A New and Novel Image Compression Algorithm Using Wavelet Footprints |
|
N. Malmurugan, A. Shanmugam, S. Jayaraman and V. V.
Dinesh Chander |
Abstract—Wavelet footprint is
a new technique that gives parsimonious representation of piecewise polynomial
signals. Using wavelet footprints we will able to exploit the inter-dependency
of wavelet coefficients across the scales around singularity locations in a
signal. In this paper, it is reported that wavelet footprints can be used to
represent images as well. We show that the images represented using footprints
require fewer coefficients, but still maintains the quality of the image and
thus provides a way for compression. The degree of the polynomial and
inter-pixel value difference threshold can be selected for possible better
minimal representation.
Index Terms— Wavelet footprints, Compression
Ratio, singularity, inter-pixel value difference threshold.
I. INTRODUCTION
The wavelet transform is a well-known
signal processing tool which has been successful to many image processing
applications. Particularly for image compression, where the transient features
of the image are represented using few scaling function coefficients whereas
the sharp nature of the image are represented using wavelet function
coefficients.
Wavelet footprint
[1] is a recent attempt to provide compact representation of piecewise
polynomial signals. These footprints exploit the inter-dependency of wavelet
coefficients across the scales around the singularities of piecewise polynomial
signals. In our work we show that wavelet footprints can be used to represent
images. Our experimental results show good compression ratios while maintaining
the visual quality of the images.
The paper is
organized as follows: Following the introduction part in section 2 we provide
an overview of wavelet footprints. In the next section we brief about the
algorithm used for signal representation using wavelet footprints. In section 4
we give the algorithm for image representation using wavelet footprints. In
section 5 we provide the experimental details and discuss the results and
finally in the last section we draw the conclusions.
II. overview of wavelet
footprints
In [1], Vitterli and Dragotti proposed a new
data structure known as wavelet footprints for modeling the discontinuities
present in the signal exactly. Also the dependency of wavelet coefficients
around the singularity locations of a piecewise polynomial signal was also
studied. It was shown that the polynomial behavior of the signal can be given
using few scaling function coefficients, whereas the non-zero wavelet
coefficients used to represent the discontinuities will be clustered around
translational locations known as the “cone of influence” [1][5].
A wavelet
footprint is a scale-space vector obtained by gathering together all the
non-zero wavelet coefficients in the cone of influence of the discontinuity and
then imposing unity norm. For a discontinuity in the signal described by
polynomials of maximum order D, the wavelet coefficients will have only (D+1)
degrees of freedom. Therefore the discontinuity is characterized by linear
combination of footprints spanning a subspace of dimension (D+1). The
collection of scaling function coefficients and wavelet footprints is known as
footprint basis.
1) Footprint Expansion for piecewise polynomial signals
The basic wavelet
expansion for a signal x[n] using periodic wavelets with atleast D vanishing
moments is given by
Let x[n] be a piecewise polynomial signal made up of polynomial pieces of
maximum degree D. Let x[n] contain single discontinuity at location k defined
mathematically as given in [1]
where the basic polynomial pieces are defined as
By selecting the
wavelet function properly with high enough vanishing moments the wavelet domain
representation of x[n] will be
where I0 and Ik represent the cone of influence at
points 0 and k respectively. Since we go in for the periodic extension of
wavelet function we will get a discontinuity at n=0. Here yjl represents the
sparser non-zero wavelet coefficients in the cone of influence of the discontinuity
k and zero. According to the definition of wavelet footprint as in [1] we
get
where fk(d)[n] represents the footprint at the discontinuity location at
n=k for the dth degree component in x[n]. For ensuring unity norm condition we
have
III. algorithm for footprint
representation
The algorithm we
used to obtain the footprint representation of piecewise polynomial signals was
suggested by Vitterli and Dragotti in [1] and this is known as the Adaptive
Depth Footprint Pursuit algorithm. In this algorithm the discontinuity
locations are estimated first and then depending upon the discontinuity
locations the maximum level of decomposition J is chosen. Since the value of J varies
depending upon the distance between the discontinuities the algorithm is
adaptive in nature. Also since we estimate the discontinuity locations well in
advance the number of iterations for the footprint representation of the
piecewise polynomial signal is considerably reduced. Detailed description of
the algorithm can found in [1] [4].
IV. extension to images
Footprints are a powerful
tool for 1-D signal compression and denoising and ample evidence of the same
was shown in [1], [2] and [3]. It is natural to extend the concept of
footprints to 2-D.
The algorithm we propose
will be a direct extension of 1-D wavelet footprints to 2-D. Here we
approximate each row or column of the image to polynomial signal using wavelet
footprints. The approximation algorithm that we follow is the Adaptive Depth
Footprint Pursuit. The proposed algorithm is as follows:
1.
Consider
each row or column in the image to be a piecewise polynomial signal.
2.
Compute
the discontinuity locations in each row. Here we go for step discontinuities
only, i.e., if the difference in the pixel values between any two neighboring
pixels is greater than a particular threshold, then that location is said to
contain discontinuity. The threshold is known as inter-pixel value difference
threshold.
3.
Collect
the estimated discontinuity locations to form the discontinuity vector K. This
vector is an input to the footprint estimation algorithm.
4.
Obtain
the footprint approximation of the corresponding row or column using the
Adaptive Depth Footprint Pursuit Algorithm.
5.
Repeat
steps 2 to 4 for all the rows.
6.
With
the approximated set of values to each row repeat steps 2 to 5 for each column.
The above procedure is shown in Fig. 1. The various parameters that
influence the results obtained using the above algorithm are the inter-pixel
value difference threshold, degree of the polynomial to which we approximate
and the size of the image. The effects of these parameters are discussed in
detail in the next section.
V. Results and Discussion
The new extension of
wavelet footprints to 2-D was implemented and tested on standard test gray
scale images. Detailed results are obtained by varying the degree of polynomial
approximation, the inter-pixel value difference threshold and by changing the size
of the images. The Peak Signal to Noise Ratio (PSNR) and the Compression Ratio
are used as the metrics to measure the performance of the algorithm.
Since there is no
quantization technique involved in this algorithm, the compression ratio is
calculated as the ratio of the original size of the image to the number of
footprint coefficients required for the representation of the entire image
along with the number of scaling function coefficients used.
Original size of the image
Compression Ratio =
----------------------------------------
(Number of
footprint coefficients)+
(Number
of scaling coefficients)
Compression Ratio and
PSNR values for varying degrees of polynomial approximation for a fixed
inter-pixel value difference threshold are tabulated in the tables I, II and
III. The threshold values are chosen arbitrarily as 30, 40 and 50. Smaller the
threshold value more will be the discontinuities located in the polynomial.
Fig.1 Flowchart for the extension of
wavelet footprints to 2-D
Table I: Degree Vs CR and Degree Vs PSNR
for inter-pixel difference threshold 30
|
Degree |
|
|
|
|||
|
CR |
PSNR |
CR |
PSNR |
CR |
PSNR |
|
|
0 |
18.2095 |
44.1334 |
17.44 |
44.207 |
299.5931 |
25.7503 |
|
1 |
11.5747 |
44.1334 |
10.96 |
44.207 |
149.7965 |
25.7503 |
|
2 |
8.4836 |
44.1334 |
7.993 |
44.207 |
99.8643 |
25.7503 |
|
3 |
6.6955 |
44.1334 |
6.289 |
44.207 |
74.89 |
25.7503 |
Table II: Degree Vs CR and Degree Vs
PSNR for inter-pixel difference threshold 40
|
Degree |
|
|
|
|||
|
CR |
PSNR |
CR |
PSNR |
CR |
PSNR |
|
|
0 |
22.637 |
44.1334 |
27.68 |
21.6946 |
477.49 |
56.6949 |
|
1 |
15.405 |
44.1334 |
20.49 |
21.6948 |
238.746 |
56.6949 |
|
2 |
11.675 |
44.1334 |
16.26 |
29.4957 |
159.16 |
56.6949 |
|
3 |
9.39987 |
44.1334 |
13.48 |
29.4957 |
119.373 |
56.6949 |
Table III: Degree Vs CR and Degree Vs
PSNR for inter-pixel difference threshold 50
|
Degree |
|
|
||
|
CR |
PSNR |
CR |
PSNR |
|
|
0 |
26.68 |
44.1334 |
32.15 |
23.411 |
|
1 |
19.412 |
44.1334 |
25.8 |
21.0641 |
|
2 |
15.255 |
44.1334 |
21.54 |
48.1676 |
|
3 |
12.56 |
44.1334 |
18.49 |
23.411 |
From the Table I, II and III,
it is interesting to note that the quality measure PSNR remains almost constant
for the variation in the degree of the polynomial, but varies considerably
depending upon the inter-pixel value difference threshold.
Fig.2 Degree
Vs CR and PSNR for
The various compression
ratios can be obtained for the same value of PSNR by fine tuning the degree of
the polynomial and the inter-pixel value difference threshold. This gives a
high degree of flexibility to handle the image for vast range of compression
ratios. When the inter-pixel value difference threshold increases the number of
discontinuities detected will decrease, thereby enabling higher compression
ratios.
Fig.3 Degree
Vs CR and PSNR for
Fig.4 Degree Vs
CR and PSNR for
Figs. 2, 3 and 4 shows
the variation of CR and PSNR with respect to the variation of the degree of the
polynomial for a constant threshold value for three different sizes of the
It can be found that the
subjective quality of the images increase as the degree of the polynomial used
for representation increases. The visual
quality of the image is a function of size of the image, inter-pixel value
difference threshold and the degree of the polynomial. Hence different
subjective qualities are possible for various combinations of these parameters.
This is evident from Figs. 5, 6 and 7.
Degree=0, Threshold = 30 Degree=1, Threshold = 30 Degree=2, Threshold = 30 Degree=3, Threshold = 30
(a) (b) (c) (d)
Degree=0, Threshold = 40 Degree=1, Threshold = 40 Degree=2 , Threshold = 40 Degree=3, Threshold = 40
(e) (f) (g) (h)
Degree=0, Threshold = 50 Degree=1, Threshold = 50 Degree=2, Threshold = 50 Degree=3, Threshold = 50
(i) (j) (k) (l)
Fig. 5 Lena128x128 for various
Degrees of Polynomial and Threshold
Degree=0, Threshold = 30 Degree=1,Threshold = 30 Degree=2, Threshold = 30 Degree=3, Threshold = 30
(a) (b) (c) (d)
Degree=0, Threshold = 40 Degree=1, Threshold = 40 Degree=2 , Threshold = 40 Degree=3, Threshold = 40
(e) (f) (g) (h)
Degree=0, Threshold = 50 Degree=1, Threshold = 50 Degree=2, Threshold = 50 Degree=3, Threshold = 50
(i) (j) (k) (l)
Fig. 6
Degree=0, Threshold = 30 Degree=1,Threshold = 30 Degree=2, Threshold = 30 Degree=3, Threshold = 30
(a) (b) (c) (d)
Degree=0, Threshold = 40 Degree=1, Threshold = 40 Degree=2 , Threshold = 40 Degree=3, Threshold = 40
(e) (f) (g) (h)
Fig. 7
VI. CONCLUSION
The new image compression technique based on wavelet
footprint is found to perform well with compression ratio as high as 477.49:1
with PSNR value = 56 db. For higher resolution images, the scheme is found to
produce excellent compression results with good image quality. Thus, we can
conclude that footprint representation is one of the good candidates for image
compression. Quantization schemes like SPIHT can be applied on footprints after
suitable modification to achieve greater compression ratios which ever
possible.
VII. Acknowledgements
The authors wish to thank the Network Project funded
by Swiss Development Cooperation (SDC) for the support extended towards the
completion of this work.
VIII. References
[1] P.L. Dragotti, M. Vetterli, “wavelet
footprints: theory, algorithms, and applications,” IEEE Transactions on Signal
Processing, vol. 51, pp.1-18, May 2003.
[2] P.L.
Dragotti and M. Vetterli, “resolution
enhancement and sampling with wavelets and footprints”, SPIE Conference on
Wavelet Applications in Signal and Image Processing, SanDeigo
[3] P.L. Dragotti, ”wavelet footprints and frames
for signal processing and communication”, PhD, dissertation, Swiss Federal
Institute of Technology, April 2002.
[4] P.L. Dragotti, M. Vetterli, V.
Velisavljevic, “directional wavelets and wavelet footprints for compression and
denoising”, International workshop on Advanced methods for multimedia signal
processing(IWDC 2002),
[5
] S. Mallat, A Wavelet Tour of
Signal Processing, Academic Press, 1998
